#include <vector>

using namespace std;

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> ans(n);
        ans[0] = 1;
        int pos[] = {0, 0, 0};
        for (int i = 1; i < n; i++) {
            int n1 = 2 * ans[pos[0]];
            int n2 = 3 * ans[pos[1]];
            int n3 = 5 * ans[pos[2]];
            int min_val = min(n1, min(n2, n3));
            if (min_val == n1) {
                ans[i] = n1;
                pos[0]++;
            }
            if (min_val == n2) {
                ans[i] = n2;
                pos[1]++;
            }
            if (min_val == n3) {
                ans[i] = n3;
                pos[2]++;
            }
        }
        return ans.back();
    }
};